/*
 * @author zzr
 * @date: 2025/10/13  17:16
 * @description: 给两个单链表的头结点 headA 和 headB 找到并返回两个单链表相交的起始节点
 * 分为三步：
 * 1. 分别求出两个链表的长度
 * 2. 较长的链表先向后走差值步
 * 3. 再同步向后走，直到找到交点
 */
public class Demo11 {
    public class ListNode {
        int val;
        ListNode next;

        ListNode(int x) {
            val = x;
            next = null;
        }
    }

    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {

        // 默认 pL 为较长链表 pS 为较短链表
        ListNode pL = headA;
        ListNode pS = headB;
        int lenA = 0;
        int lenB = 0;
        int len = 0;

        while (pL != null) {
            lenA++;
            pL = pL.next;
        }
        while (pS != null) {
            lenB++;
            pS = pS.next;
        }

        pL = headA;
        pS = headB;
        // 此时 len 的正负是未知的，进行修正
        len = lenA - lenB;

        if (len < 0) {
            // len < 0 ==> lenA 其实是较短的链表
            pS = headA;
            pL = headB;
            len = lenB - lenA;
        }
        // 经过上面的流程，一定能保证 pL 指向的是较长的链表的头节点
        // pS 指向的是较短的链表的头节点

        // 较长链表先向后走差值步
        while (len != 0) {
            pL = pL.next;
            len--;
        }

        // 找交点
        while (pL != pS) {
            pL = pL.next;
            pS = pS.next;
        }
        return pL;
    }

}
